The field of the invention is that of coding digital data belonging to one or more source data sequences to be transmitted, or broadcasted, in particular in the presence of circuit transients, and decoding coded data thus transmitted.
More precisely, this invention relates to an improvement of the coding scheme known in particular as xe2x80x9cturbo codesxe2x80x9d (registered trademark), and more particularly of the permutation implemented thereby.
The general principle of this kind of coding is introduced in particular in French patent no. FR-9 105 280, entitled xe2x80x9cProcxc3xa9dxc3xa9 de codage correcteur d""erreurs à au moins deux codages convolutifs systxc3xa9matiques parallxc3xa9les, procxc3xa9dxc3xa9 de dxc3xa9codage itxc3xa9ratif, module de dxc3xa9codage et dxc3xa9codeur correspondantsxe2x80x9d, and in the article by C. Berrou and A. Glavieux xe2x80x9cNear Optimum Error Correcting Coding and Decoding: Turbo Codesxe2x80x9d (IEEE Transactions on Communications, Volume 44, no. 10, pages 1261-1271, October 1996).
According to this technique, the implementation of xe2x80x9cparallel concatenationxe2x80x9d coding is suggested, based on using at least two elementary encoders. When decoding, this makes it possible to have two redundancy symbols from two distinct encoders. Between the two elementary encoders, a permutation means is implemented, so that each of these elementary encoders is supplied with the same digital source data, but taken in varying sequences.
An improvement of this kind of technique, for block coding (product codes), is described in the patent FR-9 313 858, and entitled xe2x80x9cTurbo dxc3xa9codage des codes produitsxe2x80x9d, as well as in the article by O. Aitsab and R. Pyndiah xe2x80x9cPerformance of Reed Solomon block turbo codexe2x80x9d (IEEE Globecom ""96 Conference, Vol. 1/3, pages 121-125, London, November 1996).
To a relatively large extent, the performance of parallel concatenation convolutional xe2x80x9cturbo codesxe2x80x9d depends on the implemented permutation function. Indeed, it appears that a non-optimized choice of this function can lead to xe2x80x9cturbo codexe2x80x9d degradation, including in particular the occurrence of a gradient change in the error rate curve below 10xe2x88x925 and 10xe2x88x926.
This phenomenon is all the more emphasized the higher the efficiency of the xe2x80x9cturbo codesxe2x80x9d under consideration, and the shorter the information blocks to be coded.
In the various documents quoted, permutation functions allowing to build xe2x80x9cturbo codesxe2x80x9d with good performance have been suggested.
In the patent FR-9 105 280, the elementary convolutional codes are binary, and permutations therefore take place directly on binary elements. More in general, many solutions for carrying out the permutation function in a parallel concatenation xe2x80x9cturbo codexe2x80x9d implementing binary convolutional codes have been suggested as part of third generation mobile phones (UMTS).
The patent FR-9 313 858, as well as the article by C. Berrou and M. Jezequel xe2x80x9cNon-binary convolutional codes for turbo codingxe2x80x9d, (Electronics Letters, Vol. 35, no. 1, pages 39-40, January 1999), also suggest using non-binary convolutional codes for building xe2x80x9cturbo codesxe2x80x9d. In this case, the permutation function therefore applies to the binary words (bit sets, e.g. pairs, or more generally n-pairs).
Generally speaking, the permutation function must of course allow to provide good dispersion of the elements from the information source and feeding the various parallel encoders, in order to create a strong random effect. Therefore, the distance properties of the composite encoder must be optimized, and in particular the minimum distance thereof maximized.
Thus, it is in particular an object of the invention to provide a parallel concatenation coding scheme (xe2x80x9cturbo codesxe2x80x9d) built from non-binary convolutional codes and having better permutation characteristics than those of known xe2x80x9cturbo codesxe2x80x9d.
More precisely, it is an object of the invention is to provide a parallel concatenation coding scheme optimizing the distance properties of the composite encoder (the xe2x80x9cturbo codexe2x80x9d), i.e. in particular maximizing the minimum distance thereof.
It is another object of the invention to provide such a coding scheme, creating a strong random effect on the data feeding the various elementary encoders, of course without modifying the dispersion effect.
It is also an object of the invention to provide such a coding scheme that is easy to implement in practice, at low cost, e.g. as an integrated circuit.
It is yet another object of the invention to provide such a coding scheme that is easy to implement for a very large number of application types.
These objects, as well as others that will be apparent more clearly hereafter, are achieved according to the invention by means of a digital source data coding scheme, implementing in parallel at least two elementary coding steps each taking into account all of said source data, and comprising a permutation step modifying the sequence of consideration of said source data between said elementary coding steps, wherein said source data is organized in source code words each comprising n binary source elements, n being greater than or equal to 2. According to the invention, said permutation step comprises:
a step of reversibly modifying the contents of at least some of said source code words, delivering modified code words;
a step of permutating the sequence of said source or modified code words.
In other words, the invention proposes to take effect at two levels, during the permutation step (the visual term of xe2x80x9cpermutationxe2x80x9d is maintained here, but the terms of xe2x80x9cshufflingxe2x80x9d, or xe2x80x9cprocessingxe2x80x9d could be used advantageously, because, as will be apparent later on, it is possible to modify the value of certain binary elements). Indeed, on the one hand, the sequence of the code words (or multiples of n), and on the other hand, the contents of the latter (intra-word modification) is acted upon.
It will be noted that word permutation can just as well be performed before or after processing the words as such.
According to an advantageous embodiment, said step of permutating the code word sequence implements a uniform permutation applied to a block of N consecutive code words.
This technique is very easy to implement, and allows to achieve almost optimal efficiency.
It can be implemented advantageously using a memory containing N code words entered in the sequence from 0 to Nxe2x88x921 and reread in the sequence from j=P.i, i varying from 0 to Nxe2x88x921, P and N mutually being prime numbers.
Preferably, in this case, P is close to N.
According to a preferred approach of the invention, said contents modification is applied only to some of said code words. E.g., said contents modification is applied to every other code word.
Advantageously, said contents modification comprises a permutation of the sequence of binary elements within the code word under consideration.
According to another advantageous aspect, said contents modification comprises replacing at least one of the binary source elements of the code word under consideration with a combination of at least two of said binary source elements.
Said code words can in particular be pairs. However, they can of course more generally be multiples of n, whatever the value of n, greater than or equal to 2.
In the case of pairs, the combinations can associate with the source pair {a,b} at least one of the following modified pairs:
(a,b)
(b,a)
(a+b,b)
(b,a+b)
(a,a+b)
(a+b,a)